package dp;

public class D230816 {
    // 跳台阶
    public int jumpFloor (int number) {
        int f1 = 1;
        int f2 = 1;
        int res = 1;
        for (int i = 2; i <= number; i++) {
            res = f1 + f2;
            f2 = f1;
            f1 = res;
        }
        return res;
    }


    // 最小花费的爬楼梯
    // 使用一个数组，记录爬到第 i 阶的最小花费
    // 初始状态：因为可以从第 0 个台阶，或第 1 个台阶开始
    // 所以 dp[0] = 0 dp[1] = 0
    // 状态转移：因为花费一次可以走一个或两个台阶
    // 所以 取 dp[i-1] + cost[i-1] 和 dp[i-2] + cost[i-2] 的较小值，作为 dp[i]
    public int minCostClimbingStairs (int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[n];
    }


    // 最长公共子序列(二)
    // 因为要返回的不是子序列的长度，而是最长子序列
    // 所以数组记录的不是长度，而是子序列
    public String LCS (String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        // 多定义一行一列
        String[][] dp = new String[n + 1][m + 1];
        // 初始化第一行和第一列
        for (int i = 0; i <= n; i++) {
            dp[i][0] = "";
        }
        for (int i = 0; i <= m; i++) {
            dp[0][i] = "";
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    // 相等，数组左上方的子序列 拼接 当前的 字符
                    dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1);
                } else {
                    // 不相等，左边 和 上边，选择一个长的子序列
                    dp[i][j] =
                            dp[i - 1][j].length() > dp[i][j - 1].length()
                                    ? dp[i - 1][j] : dp[i][j - 1];
                }
            }
        }
        // 结果 dp[n][m]
        // 如果是 “”，说明没有子序列 返回 -1
        return dp[n][m].equals("") ? "-1" : dp[n][m];
    }


    // 这个解法可能会更 省空间
    // 不记录子序列，记录长度 和 选择的方向（状态转移时，相等 左上方-1，不相等 左边-2 或 上边-3）
    private String x = "";
    private String y = "";
    //获取最长公共子序列
    String ans(int i, int j, int[][] b){
        String res = "";
        //递归终止条件
        if(i == 0 || j == 0)
            return res;
        //根据方向，往前递归，然后添加本级字符
        if(b[i][j] == 1){
            res += ans(i - 1, j - 1, b);
            // 等于 1，来自左上方，就说明是相等的，增加了新字符
            res += x.charAt(i - 1);
        }
        else if(b[i][j] == 2)
            // 来自左边，没有新字符
            res += ans(i - 1, j, b);
        else if(b[i][j] == 3)
            // 来自上边，没有新字符
            res += ans(i,j - 1, b);
        return res;
    }
    public String LCS2 (String s1, String s2) {
        //特殊情况
        if(s1.length() == 0 || s2.length() == 0)
            return "-1";
        int len1 = s1.length();
        int len2 = s2.length();
        x = s1;
        y = s2;
        //dp[i][j]表示第一个字符串到第i位，第二个字符串到第j位为止的最长公共子序列长度
        int[][] dp = new int[len1 + 1][len2 + 1];
        //动态规划数组相加的方向
        int[][] b = new int[len1 + 1][len2 + 1];
        //遍历两个字符串每个位置求的最长长度
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                //遇到两个字符相等
                if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                    //考虑由二者都向前一位
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    //来自于左上方
                    b[i][j] = 1;
                }
                //遇到的两个字符不同
                else{
                    //左边的选择更大，即第一个字符串后退一位
                    if(dp[i - 1][j] > dp[i][j - 1]){
                        dp[i][j] = dp[i - 1][j];
                        //来自于左方
                        b[i][j] = 2;
                    }
                    //右边的选择更大，即第二个字符串后退一位
                    else{
                        dp[i][j] = dp[i][j - 1];
                        //来自于上方
                        b[i][j] = 3;
                    }
                }
            }
        }
        //获取答案字符串
        String res = ans(len1, len2, b);
        //检查答案是否位空
        if(res.isEmpty())
            return "-1";
        else
            return res;
    }
}
